COMMENT ⊗   VALID 00014 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	3.0	Geometric Modeling Theory.
C00008 00003	3.1	Kinds of Geometric Models.
C00010 00004	
C00014 00005		
C00017 00006	
C00020 00007		
C00023 00008	
C00026 00009	
C00028 00010	3.2	Polyhedron Definitions.
C00031 00011	
C00048 00012	3.3	Camera, Light and Image Modeling.
C00049 00013	First there is the camera lens center locus:
C00071 00014	
C00073 ENDMK
C⊗;
3.0	Geometric Modeling Theory.

	3.1	Kinds of Geometric Models.
	3.2	Polyhedron Modeling.
	3.3	Camera, Light and Image Modeling.

3.0	Introduction.

	In  the specific  context of  computer  vision and  graphics,
geometric modeling refers to constructing computer representations of
physical objects,    cameras,   images  and  light for  the  sake  of
simulating their behavior. In the context of Artificial Intelligence,
a  geometric model  is a  kind of  world model;  ignoring subtleties,
geometric world modeling  is distinguished from semantic  and logical
world modeling  in that it is quantitative  and numerical rather than
qualitative and symbolic.   The notion of a  world model requires  an
external  world environment  to  be modeled,    an internal  computer
environment to  hold the model,  and a  task performing entity to use
the model.  In  the context  of  geometry,  modeling is  a  synthetic
problem,  like a construction  with ruler and straight edge, modeling
problems  require an  algorithmic solution  rather than a  proof. The
adjective "geometric" however is  quite apropos in that  it literally
means "world measure" which is exactly the activity to be automated.
3.1	Kinds of Geometric Models.
	
	The main  problem  of geometric  modeling is  to invent  good
methods for representing  arbitrary physical objects in a computer. A
physical object (for the moment) is something solid, rigid,   opaque,
Newtonian and macroscopic with a mathematically well behaved surface.
Physical objects  include: the earth, chairs, roads,  and plastic toy
horses.  In addition,  physical objects may be  moved about in space,
but two objects  can not simultaneously occupy the  same space at the
same time.  The scope of the problem can be appreciated by  examining
the virtues and drawbacks of the kinds of models listed in the box.

---------------------------------------------------------
| TEN KINDS OF GEOMETRIC MODELS:			|
|							|
| Space Oriented:					|
|							|
|	1. 3-D Space Array.				|
|	2. Recursive Cells.				|
|	3. 3-D Density Function.			|
|	4. 2-D Surface Functions.			|
|	5. Parametric Surface Functions.		|
|							|
| Object Oriented:					|
|							|
|	6. Manifolds.					|
|	7. Polyhedra.					|
|	8. Volume Elements.				|
|	9. Cross Sections.				|
|      10. Skeletons.					|
---------------------------------------------------------

	For a naive start,  first consider a  3-D array in which each
element indicates  the presence or absence of  solid matter in a cube
of space.  Such a 3-D  space array has the very desirible  properties
of "spatial addressing" and "spatial uniqueness" in their most direct
and  natural form. Spatial addressing refers  to finding out what the
model  contains  within a  distance  R  of  a  locus  X,Y,Z;  spatial
uniqueness refers  to modeling the property that  physical solids can
not occupy the same space. The  main drawback of the 3-D space  array
model is illustrated by the apparently legal FORTRAN statement:

		DIMENSION SPACE(10000,10000,10000)

The problem with  such a dimension  statement is that no  present day
computer  memory is large  enough to  contain a 10↑15  element array.
Smaller space arrays  arrays can  be useful but  necessarily can  not
model large volumes with high resolution. A further drawback of space
arrays  is that  objects and surfaces  are not  readily accessible as
entities; that  is  a  space array  lacks the desirible  property  of
"object coherence".

	The space array idea  can be salvaged (and must  be salvaged)
by noticing that  large portions of the array contain similar values.
By grouping blocks of  elements with the  same values together,   the
addressing process  becomes more  complicated but the  overall memory
required is reduced and the two desired properties can be maintained.
One  way  of  doing  this  (which  has  been  discovered  in  several
applications) is "recursive cells";  the whole space is considered to
be a cell; if  the space is  not homogeneous than  the first cell  is
divided into two  (or four or eight)  sub cells and the  criterion is
applied again. This technique of recursive celling allows the spatial
sorting of objects,  if the  object models can be subdivided at  each
recursion without losing the properties of the objects.
	
	In  mathematical physics,    arbitrary physical  objects  are
frequently  referred   to  as  three  dimensional  density  functions
W=RHO(X,Y,Z). Unfortunately such density functions can not be written
out for  objects such as  a typing chair  or a plastic  horse without
resorting  to a programming language or  an extensive table (which is
equivalent to the space  array model).  Some special  objects however
are essentially  2-D and can be  approximated by surface  funtion Z =
F(X,Y). For example geodetic  maps have been  handled by computer  in
such a fashion.

	By definition, a function is  single valued; consequently the
description of even modestly complicated objects can not be expressed
directly  as  a  single  function  of  orthogonal  rectilinear  space
coordinates X,   Y and Z. It is necessary  either to adopt parametric
functions  or  to subdivide  the  object  into portions  that  can be
described by  simple  functions of  Cartesian  variables. The  latter
course  of subdividing objects  into portions is  called segmentation
and is discussed later; the former  course can be illustrated by  the
example in figure **  showing (X,Y,Z) locus of the surface  of a unit
cube  expressed  as  functions of  (U,V)  surface  coordinates.   The
advantage of parametric  functions is  that extended arbitrary  curve
surfaces  can  be  expressed;  some of  the  disadvantages  are  that
parametric  curves may be  self intersecting,   they are  not easy to
modified locally,   and  the functions  become impractically  complex
before interesting objects are achieved.

	At this point, we  pass from space oriented models  to object
oriented models. I  wish to point out the mysterious dicotomy between
objects and the space that contains the objects, and observe that the
same dichotomy appears in the foundations  of physics.  However,  our
goal is  merely to simulate the properties of objects; rather than to
explain them.   In  this regard,    the representation  of time  will
receive  no special attention;  although an advanced  problem solving
robot will want to run  world simulations along multiple time  paths,
the present  discussion will be  restricted to simulations  along one
time path.

	After existence in  space and time, another  general property
of physical  objects is that they can be  enclosed by an unbroken two
dimensional surface  with an unabiguous  inside and  outside.   Which
brings  us to  the  mathematical  topic (celebrated  in  song by  Tom
Lehrer) of the algebraic topology of locally Euclidean transitions of
infinitely differentiable oriented  Riemann manifolds. A manifold  is
the mathematical  abstraction of a surface; a  Riemann manifold has a
metric function; an oriented manifold has a unambiguous inside and an
outside; the phrase "infinitely differentiable" can  be taken to mean
that  the surface is smooth  and continuous; and  the phrase "locally
Euclidean transitions" refers to the process of segmenting the object
into  portions   that  can  be  approximated   by  relatively  simple
functions. In  particular,  the 2-D Riemann (sub)manifold embedded in
3-D Euclidean space is the mathematical object that  comes closest to
representing  the  shape  and  extent  of  a  physical  object;  such
manifolds lead directly to the topology of surfaces which in turn  is
a convenient computational approach to polyhedra.
	
	The topology of a  2-D Riemann submanifold embedded in  a 3-D
Euclidean space is  composed of three kinds of simplex: the 0-Simplex
(or  vertex), the  1-Simplex  (or  edge),    and  the  2-Simplex  (or
triangle). In topological analysis,  it may be demonstrated that such
2-D Riemann submanifolds may be divided into simplex such that Eulers
equations  F-E+V=2-2*H  is  satisfied  (where  F  is  the  number  of
2-simplex,   E  is  the number  of 1-simplex,    V is  the  number of
0-simplex and H is  the genus (number of  handles) of the  manifold);
and such  that the  surface of  the manifold  can be approximated  by
local  functions over  each 2-simplex which  are Euclidean  and which
splice  together  correctly  at  all  the  1-simplex  (edges).     By
introducing  a  sufficient  (but  finite)  number  of  triangles  the
manifold  can  be  approximated to  within  an  epsilon,  by constant
functions; yielding the geometric object called the "polyhedron".

	The main  inherent advantage  of  a polyhedral  model is  its
coherent  surface topology of  faces,   edges and  vertices.   Such a
surface can  be  subdivided  without  losing  its  coherence  or  the
coherence of the object.  The disadvantages  of polyhedra include the
lack  of  spatial uniqueness  and  spatial  addressing; necessitating
computation to be done to detect and prevent spatial conflict  and to
find the  portions of an  entity occupying  a given volume.   Another
disadvantage  is  that  polyhedra per  se  are  not  curved surfaces,
however by associating an appropriate function with each face a model
of  a 2-D Riemann  manifold can be  made,   which is a  curved object
representation. 

	Arbitrary objects can also be  described by listing a set  of
cross sections taken at  a sufficient number of cutting  planes; this
is how the shape of a ship's hull or an airplane's wing is specified.
Cross sections have the interesting feature of good space modeling on
one  axis.   Forsaking arbitrary  shaped objects,   large  classes of
things  can be  described in  terms of  a small  set of  basic volume
elements.   For  example, Roberts  and others  have  built models  of
familar objects  using only rectangular and  triangular right prisms.
Although,   arbitrary  solid  polyhedra can  be  constructed  out  of
tetrahedrons (the 3-simplex);  no significant modeling  system exists
using this potentially interesting approach.

	Skeletal  models are  based on abstracting  an object  into a
stick figure and by associating  a diameter or set of cross  sections
with the sticks. In particular,  spine cross section models have been
pursued  at Stanford by (Agin,   Binford and  Nervatia; Blum).  Spine
cross section models have the advantage of being able to express many
objects in a concise  form suitable  for recognition,   however spine
cross section models can not  be used directly for arbitrary  shapes.
Finally,  it is  useful to represent physical objects by  a very weak
model such as by  using sets of spheres or sets of surface points. It
is  interesting  to  note  that  the  "reality"  that  the  robot  in
Winograd's thesis  could talk about,   was a blocks world  based on a
geometric model  consisting of points, size of block, and a two paged
LISP routine named FINDSPACE.

	To the best of  my knowledge, this survey is  complete; there
are no  other significantly different kinds  of geometric models. The
desirable properties that have turned up in this survey  are included
in the list below. The final desirable property is that there be some
hope  that the computer can  derive the model  by measurements it can
make itself, although it is quite likely that one  model will be best
for input and another model will be best for simulation.

---------------------------------------------------------------------
DESIRABLE PROPERTIES OF A GEOMETRIC MODEL.

	1. Spatial Addressing.
	2. Spatial Uniqueness.
	3. Object Coherence with Divisibility.
	4. Surface Coherence with Divisibility.
	5. Shape generality.
	6. Large Extent with High Resolution.
	7. Readily Modifiable.
	8. Suitable for photometric, kinematic and dynamic simulation.
	9. Feasible memory and computation requirements.
       10. Potential for automatic model acquistion.
---------------------------------------------------------------------
3.2	Polyhedron Definitions.

	There are several ways to define  the word "polyhedron", each
distinct  definition emphases  a different aspect  of the  concept so
that  the simple  forms  of  the  definitions  fall  short  of  being
equivalent.

	Topologically, the  surface elements of  a polyhedron  forms a
graph that  satisfies Euler's F-E+V=2-2*H equation; where  F, E and V
are the number of faces,   edges and vertices of the polyhedron;  and
where  H is  the number  of holes  in (or  genus of)  the polyhedron.
However,  not  all  Eulerian  graphs  of  faces,  edges and  vertices
correspond to solid polyhedra.

	Geometrically,   a polyhedron  is a  simply connected  finite
region  of space composed of  the union of a  finite number of convex
polyhedra. A  convex polyhedron  is a  non  empty, simply  connected,
finite region  of space enclosed by  a finite number of  planes.  The
boundary  of  the  polyhedron  is called  its  surface.    The simply
connected regions  of the  surface belonging  to only  one plane  are
called faces.  The simply connected regions of  the surface belonging
to exactly two planes are called  edges; and the loci of the  surface
where three or more planes interect are called vertices.

_____________________________________________________________________
Properties of a Solid Polyhedron:

EULER		1. Satisfies Eulers Equation F-E+V=2*B-2*H
TRIVALENCE	2. All vertices and faces have three or more edges.
NON-SELF-	3. No edge intersects a face or vertex
INTERSECTION.	    to which it is not topologically linked.
FACE PLANARITY	4. All the vertices of a face are coplanar.
SOLIDITY	5. The volume measure is finite and positive.
(FACE CONVEXITY	6. All the faces are convex.)
__________________________________________________________
3.3	Camera, Light and Image Modeling.
	
	Common to both computer graphics and  vision is the necessity
to  model  the cameras,  light and  images  so that  pictures  may be
synthesized or analysized.

The following  camera  model has  nearly  become  a standard  can  be
specified by  nine real  numbers: three  coordinates of  locus, three
coordinates  of orientation,  image aspect  ratio, image  focal plane
distance and pixel spot size.
First there is the camera lens center locus:

		CX, CY, CZ,	in world coordinates.

Afixed to the lens center is the camera frame of reference with  unit
vectors  i, j and k. When the image formed by the camera is placed in
correspondence to a display screen, the
unit  vector  i  maps  into  the  rightward positive x of the display
screen, and the unit vector j maps into the upward positive y of  the
display screen, and the unit vector k comes out of the display screen
to form a right handed coordinate system.  Together  the  three  unit
vectors of the camera are the three by three rotation matrix:

		IX, IY, IZ
		JX, JY, JZ	in world coordinates.
		KX, KY, KZ

Next,  there  are  three  scales  which  determine the correspondence
between world size and image size. Observe that the world is measured
in physical units of length like meters or feet while computer images
come in integral sizes like 1024 by 1024 or 480 rows by 512  columns,
thus  the  conversion  scales must be in terms of logical image units
per physical world units.   In an actual television camera  a  minute
image  (say  9mm  by 12mm) is formed on a vidicon tube and that image
has a particular number of rows and columns. It is the  little  image
on the vidicon that we pretend to model by the six parameters:

		LDX, LDY, LDZ		Logical raster size.
		PDX, PDY, FOCAL		Physical raster size.

Where the number named FOCAL, is the focal plane  distance  which  in
this model (with distant objects) can safely be equated with the lens
focal length and can be given in millimeters (conventional  lens  run
12.5mm  to  75mm for 1" TV).   The integer LDZ is an artifact so that
the units come out correctly in the  Z  dimension.  Thus  the  scales
factors are defined:

		SCALEX ← -FOCAL*LDX/PDX;
		SCALEY ← -FOCAL*LDY/PDY;
		SCALEZ ←  FOCAL*LDZ;

	The light scattering  properties of ordinary surfaces  can be
modeled  by thinking  of  the surface  as composed  of  `zillions' of
little mirrors. The  orientation of each mirror  is described by  two
angles,  its tilt  from the normal vector of the  surface and its pan
about the  normal vector with respect to a specified reference vector
in the tangent plane of the surface. For a perfect reflecting surface
all the differential mirrors have  a zero pan and tilt; for isotropic
conventional   surfaces   the   statistical   distribution   of   pan
orientations is flat and  the distribution of tilt orientations  is a
blip function; and  for a perfect isotropic Lambert surfaces both the
pan and tilt distributions are flat.